package test.n00000;

public class Problem00050 {
    public static void main(String[] args) {
        println("babad");
        println("cbbd");
        println("bb");
        println("babad");
        println("aacabdkacaa");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.longestPalindrome(s));
    }

    public static class Solution {
        /**
         * 给你一个字符串 s，找到 s 中最长的回文子串。
         * <p>
         * 解题方法:(暴力法+中心扩散)
         * 取字符串中间的字符，依次左右定位，判断最大回文
         *
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
            String max = s.substring(0, 1);
            System.out.println(s);

            for (int i = 1; i < s.length(); i++) {
                String t = longestPalindrome(s, i);
                if (t.length() > max.length()) {
                    max = t;
                }
            }
            return max;
        }

        public static String longestPalindrome(String s, int position) {
            String m = "";

            // mid
            for (int i = 0; i < position; i++) {
                if (position + 1 + i >= s.length()) {
                    break;
                }
                if (s.charAt(position - 1 - i) == s.charAt(position + 1 + i)) {
                    String t = s.substring(position - 1 - i, position + 1 + i + 1);
                    if (t.length() > m.length()) {
                        m = t;
                    }
                } else {
                    break;
                }
            }

            // right inner middle
            for (int i = 0; i < position; i++) {
                if (position + 1 + i >= s.length()) {
                    break;
                }
                // right middle
                if (s.charAt(position - i) == s.charAt(position + 1 + i)) {
                    String t = s.substring(position - i, position + 1 + i + 1);
                    if (t.length() > m.length()) {
                        m = t;
                    }
                } else {
                    break;
                }
            }

            // left inner middle
            for (int i = 0; i < position; i++) {
                if (position + i >= s.length()) {
                    break;
                }

                if (s.charAt(position - 1 - i) == s.charAt(position + i)) {
                    String t = s.substring(position - 1 - i, position + i + 1);
                    if (t.length() > m.length()) {
                        m = t;
                    }
                } else {
                    break;
                }
            }

            return m;
        }
    }
}
